/* 用 a + b 与 b + a 比较大小排序
 * 将数组转换为字符串
 * 排序判断规则：若 x + y > y + x，则 x > y
 *              若 x + y < y + x，则 x < y
 * 例如：3 30 > 30 3
 * 所以 30 < 3
 */

// 根据算法，如果a < b，那么a排在b前面，否则b排在a前面
// 可利用反证法，假设排成的最小数字为xxxxxx，并且至少存在一对字符串满足这个关系：a > b，
// 但是在组成的数字中a排在b前面。根据a和b出现的位置，分三种情况考虑：
// （1）xxxxab，用ba代替ab可以得到xxxxba，这个数字是小于xxxxab，与假设矛盾
// 因此排成的最小数字中，不存在上述假设的关系。

// （2）abxxxx，用ba代替ab可以得到baxxxx，这个数字是小于abxxxx，与假设矛盾
// 因此排成的最小数字中，不存在上述假设的关系。

// （3）axxxxb，这一步证明麻烦了一点。可以将中间部分看成一个整体ayb，则有ay < ya，yb < by成立
// 将ay和by表示成10进制数字形式，则有下述关系式，这里a，y，b的位数分别为n，m，k

//   关系1: ay < ya => a * 10^m + y < y * 10^n + a =>
//          a * 10^m - a < y * 10^n - y => a( 10^m - 1)/( 10^n - 1) < y

//   关系2： yb < by => y * 10^k + b < b * 10^m + y =>
//           y * 10^k - y < b * 10^m - b => y < b( 10^m -1)/( 10^k -1)

//   关系3： a( 10^m - 1)/( 10^n - 1) < y < b( 10^m -1)/( 10^k -1)  =>
//           a/( 10^n - 1)< b/( 10^k -1) => a*10^k - a < b * 10^n - b =>a*10^k + b < b * 10^n + a => a < b

// 这与假设a > b矛盾。因此排成的最小数字中，不存在上述假设的关系。

// 综上所述，得出假设不成立，从而得出结论：对于排成的最小数字，
// 不存在满足下述关系的一对字符串：a > b，但是在组成的数字中a出现在b的前面。从而得出算法是正确的

var minNumber = function (nums) {
  let left = 0;
  let right = nums.length - 1;
  quickSort(nums, left, right);
  return nums.join("");

  function quickSort(nums, left, right) {
    if (left > right) return;
    let mid = partition(nums, left, right);
    quickSort(nums, left, mid - 1);
    quickSort(nums, mid + 1, right);
  }

  function partition(nums, left, right) {
    let i = left + 1,
      j = right;
    let pivot = nums[left];
    while (i <= j) {
      while (i <= j && !compare(nums[i], pivot)) i++;
      while (i <= j && compare(nums[j], pivot)) j--;
      if (i <= j) {
        let temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
      }
    }
    nums[left] = nums[j];
    nums[j] = pivot;
    return j;
  }

  function compare(a, b) {
    let s1 = a + "" + b;
    let s2 = b + "" + a;
    if (parseInt(s1, 10) > parseInt(s2, 10)) return true;
    return false;
  }
};
